package test.base.arithmetic.innersort;

/**
 * 插入排序
 * @filename      : InsertSort.java
 * @description   : TODO(一句话描述该类做什么)
 * @author        : wanghongkai
 * @create        : 2013-6-8 下午2:41:28
 * @copyright     : hileto Corporation 2013
 *
 * Modification History:
 * Date             Author       Version
 * --------------------------------------
 * 2013-6-8 下午2:41:28
 */
public class InsertSort {
	public static void insertSort(int[] arr){
		if(arr != null && arr.length > 0){
			int[] newArr=new int[arr.length];
			newArr[0]=arr[0];
			int nowTotalcount=1;//有效元素的个数(第一位有个赋值，所以初始为1)
			Long begin=System.currentTimeMillis();
			for(int i=1;i<arr.length;i++){
				for(int j=0;j<newArr.length;j++){
					if(arr[i] < newArr[j]){//与新集合比对，小于则先指定位置平移，然后放入指定值
						reSort(newArr,j);
						newArr[j]=arr[i];
						nowTotalcount++;
						break;
					}else{
						if(j==nowTotalcount){//如果一直不小于，则放到该位置
							newArr[j]=arr[i];
							nowTotalcount++;
							break;
						}
					}
				}
			}
			Long end=System.currentTimeMillis();
			SortTools.println(newArr, "插入算法", end-begin);
		}
	}
	
	/**
	 * 重新排序(指定位置后的元素后移一位)
	 */
	private static void reSort(int[] arr,int index){
		for(int i=arr.length-1;i>index;i--){
			arr[i]=arr[i-1];
		}
		arr[index]=0;
	}
}
